package list

import "abdis/interface/datastruct"

type node struct {
	val  any
	prev *node
	next *node
}

type LinkedList struct {
	first *node
	last  *node
	size  int
}

func MakeLinkedList() *LinkedList {
	return &LinkedList{
		first: nil,
		last:  nil,
		size:  0,
	}
}

func (l *LinkedList) checkValid() {
	if l == nil {
		panic("list is nil")
	}
}

func (l *LinkedList) find(index int) *node {
	n := l.first
	for i := 0; i < index; i++ {
		n = n.next
	}
	return n
}

func (l *LinkedList) removeNode(n *node) {
	if n.prev == nil {
		// head node
		l.first = n.next
	} else {
		n.prev.next = n.next
	}

	if n.next == nil {
		// tail node
		l.last = n.prev
	} else {
		n.next.prev = n.prev
	}

	// for gc
	n.prev = nil
	n.next = nil
	l.size--
}

func (l *LinkedList) Add(val any) {
	l.checkValid()

	n := &node{
		val: val,
	}

	l.size++

	if l.size == 1 {
		l.first = n
		l.last = n
		return
	}

	n.prev = l.last
	l.last.next = n
	l.last = n
}

func (l *LinkedList) Insert(index int, val any) {
	l.checkValid()

	if index < 0 || index > l.size {
		panic("index out of range")
	}

	if index == l.size {
		l.Add(val)
		return
	}

	pivot := l.find(index)

	n := &node{
		val:  val,
		prev: pivot.prev,
		next: pivot,
	}

	if pivot.prev == nil {
		l.first = n
	} else {
		pivot.prev.next = n
	}
	pivot.prev = n
	l.size++
}

func (l *LinkedList) Len() int {
	l.checkValid()
	return l.size
}

func (l *LinkedList) Range(start int, stop int) []any {
	l.checkValid()
	if start < 0 || start >= l.size || stop < start || stop > l.size {
		panic("out of range")
	}

	size := stop - start
	slice := make([]any, size)

	n := l.find(start)
	for i := 0; i < size; i++ {
		slice[i] = n.val
		n = n.next
	}
	return slice
}

func (l *LinkedList) Remove(index int) any {
	l.checkValid()

	if index < 0 || index >= l.size {
		panic("index out of range")
	}

	n := l.find(index)
	l.removeNode(n)
	return n.val
}

func (l *LinkedList) RemoveLast() any {
	l.checkValid()
	if l.last == nil {
		return nil
	}
	n := l.last
	l.removeNode(n)
	return n.val
}

// RemoveAllByVal removes all elements with the given val
func (l *LinkedList) RemoveAllByVal(expected datastruct.Expected) int {
	if l == nil {
		panic("list is nil")
	}
	n := l.first
	removed := 0
	var nextNode *node
	for n != nil {
		nextNode = n.next
		if expected(n.val) {
			l.removeNode(n)
			removed++
		}
		n = nextNode
	}
	return removed
}

// RemoveByVal removes at most `count` values of the specified value in this list
// scan from left to right
func (l *LinkedList) RemoveByVal(expected datastruct.Expected, count int) int {
	if l == nil {
		panic("list is nil")
	}
	n := l.first
	removed := 0
	var nextNode *node
	for n != nil {
		nextNode = n.next
		if expected(n.val) {
			l.removeNode(n)
			removed++
		}
		if removed == count {
			break
		}
		n = nextNode
	}
	return removed
}

// ReverseRemoveByVal removes at most `count` values of the specified value in this list
// scan from right to left
func (l *LinkedList) ReverseRemoveByVal(expected datastruct.Expected, count int) int {
	if l == nil {
		panic("list is nil")
	}
	n := l.last
	removed := 0
	var prevNode *node
	for n != nil {
		prevNode = n.prev
		if expected(n.val) {
			l.removeNode(n)
			removed++
		}
		if removed == count {
			break
		}
		n = prevNode
	}
	return removed
}

func (l *LinkedList) Get(index int) any {
	l.checkValid()
	if index < 0 || index >= l.size {
		panic("index is out of range")
	}

	return l.find(index).val
}

func (l *LinkedList) Set(index int, val any) {
	l.checkValid()
	l.find(index).val = val
}

func (l *LinkedList) ForEach(consumer datastruct.Consumer) {
	l.checkValid()
	n := l.first
	for n != nil {
		flag := consumer("", n.val)
		if !flag {
			break
		}
		n = n.next
	}
}
